package Q784;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 字母大小写全排列
 *
 * @author 23737
 * @time 2021.12.1
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().letterCasePermutation("a1b2"));
    }
}

/**
 * 回溯
 * 不是这种写法！！题目理解错了
 */
class Solution_fail {

    private List<String> list;

    public List<String> letterCasePermutation(String s) {
        list = new ArrayList<>();
        if (s.length() == 0) {
            return list;
        }
        Deque<Character> path = new LinkedList<>();
        boolean[] used = new boolean[s.length()];
        dfs(s, path, used, 0, s.length());
        return list;
    }

    private void dfs(String s, Deque<Character> path, boolean[] used, int depth, int length) {
        if (depth == length) {
            list.add(path.toString());
        }
        for (int i = 0; i < length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.addFirst(s.charAt(i));
            dfs(s, path, used, i + 1, length);
            path.removeLast();
            used[i] = false;
        }
    }
}

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<StringBuilder> ans = new ArrayList();
        ans.add(new StringBuilder());

        for (char c : S.toCharArray()) {
            int n = ans.size();
            System.out.println("size --- > " + n);
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.add(new StringBuilder(ans.get(i)));
                    ans.get(i).append(Character.toLowerCase(c));
                    ans.get(n + i).append(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; ++i)
                    ans.get(i).append(c);
            }
        }

        List<String> finalans = new ArrayList();
        for (StringBuilder sb : ans)
            finalans.add(sb.toString());
        return finalans;
    }
}
